class Solution {
public:
    int dp[50][50];
    int sum(const vector<int> &nums, int L, int R) {
        int sum = 0;
        for(int i = L; i <= R; i++) {
            sum += nums[i-1];
        }
        return sum;
    }
    int dfs(int L, int R, const vector<int> &nums) {
        if(dp[L][R] != -1) {
            return dp[L][R];
        }
        if(L == R) {
            return dp[L][R] = nums[L-1];
        }
        return dp[L][R] = sum(nums, L, R) - min(dfs(L+1, R, nums), dfs(L, R-1, nums));
    }
    bool PredictTheWinner(vector<int>& nums) {
        memset(dp, -1, sizeof(dp));
        return dfs(1, nums.size(), nums)*2 >= sum(nums, 1, nums.size());
    }
};
